/*
	本程序采用了多叉树的结构，在构造方面比较复杂。
*/

#include<stdio.h>
#include<stdlib.h>
#include"dirtree.h"

int main()
{

	int n,i,t1,t2;
	char path[255];
	char *t;
	Node *node,start,*temp,*temp1,*temp2;
	Init(&start);
	scanf("%d",&n);
	
	for(i=0;i<n;i++)
	{
		temp=&start;
		int k[127]={0};
		t1=0;
		t2=1;
		scanf("%s",path);
		k[0]=-1;
		while(path[t1]!=0)//当字符为0的时候，也就是结束的时候
		{
			if(path[t1]=='/')
			{
				k[t2]=t1;//标记'/'所在的位置
				t2++;//下一个
			}
			t1++;
		}
		k[t2]=t1;//存储结束时的序号。
		
		t1=0;
		do
		{
			t=malloc(k[t1+1]-k[t1]+2*t1+1);
			copy(t,path,k[t1]+1,k[t1+1],t1);
			t1++;
			node=malloc(sizeof(Node));
			Init(node);
			node->p=t;//节点创建成功,此时，没有确定四周节点的关系
			node->u=temp;//确定节点纵向关系

			if(temp->d)
			{
				temp2=temp->d;
				while(temp2->n)
				{
					t2=comp(temp2->n->p,node->p);//比较temp2横向节点中下一个节点与node的大小。
					if(t2==-1)//temp2横向节点中下一个节点较大，node较小，而且没有相同的路径，因此需要创建一个新的树杈。
					{
						temp1=temp2->n;
						temp2->n=node;
						node->n=temp1;
						node->pr=temp2;
						temp1->pr=node;
						break;
					}//第一种情况，位于队中
					if(t2==0)
					{
						if(node)
							free(node);
						break;	//找到对应路径所对应的树，temp横向节点中下一个节点与node相同;但是temp2->n->d可能存在
					}//第二种情况，已经存在
					temp2=temp2->n;
				}
				
				if(temp2->n==NULL)//若下一个节点是空节点，则表明没有重复的路径，且该节点在此目录中最大，需要在目录尾部创建一个新的树杈。
				{
					temp2->n=node;
					node->pr=temp2;
				}//第三种情况，位于队尾
				temp=temp2->n;//此时，temp必定会有节点
			}
			else 
			{
				Node *temp3=malloc(sizeof(Node));
				Init(temp3);
				temp3->u=temp;
				temp->d=temp3;//排头兵
				temp3->n=node;
				node->pr=temp3;
				temp=node;
			}//第四种情况，位于队头
			
		}while(k[t1+1]!=0);
	}//创建目录树
	Traversal(&start);		
}
